#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;

struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode() : val(0), left(nullptr), right(nullptr) {}
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
	TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
	unordered_map<int, int> map;
	vector<int> pre;
	TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
		for (int i = 0; i < inorder.size(); i++)
			map[inorder[i]] = i;
		pre = preorder;
		TreeNode *root = buildTree(0,preorder.size()-1,0,inorder.size()-1);
		return root;
	}

	TreeNode* buildTree(int pre_left, int pre_right,int in_left, int in_right) {
		if (in_left > in_right || pre_left > pre_right) return NULL;
		int root = pre[pre_left];
		int root_pos = map[root];
		TreeNode *node=new TreeNode(root);
		node->left = buildTree(pre_left+1,pre_left+root_pos-in_left, in_left ,root_pos-1 );
		node->right = buildTree(pre_left+root_pos-in_left+1,pre_right,root_pos+1,in_right);
		return node;
	}

};

void main() {
	Solution s;
	vector<int> pre = { 3,9,20,15,7 };
	vector<int> in = { 9,3,15,20,7 };
	s.buildTree(pre,in);
}